home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / pdsrt211.arc / QUICKER.C < prev    next >
Text File  |  1990-06-18  |  5KB  |  141 lines
  1. /* quicker.c --  Improved Quicksort algorithm    */
  2.  
  3. /*
  4.  *  The Quicksort algorithm was invented in 1960 by C. A. R. Hoare.  Since  *
  5.  *  then, it has been analyzed and studied by many people,  it is probably  *
  6.  *  the  most  thoroughly  analyzed  of  any  of  the  sorting algorithms.  *
  7.  *  Numerous "improvements" to the basic Qicksort algorithm have  appeared  *
  8.  *  in  the  literature  however  only  a  few  have  real  benefit.   The  *
  9.  *  "improvements" in this implementation have  been  documented  by  many  *
  10.  *  people  but  I followed Robert Sedgewick as presented in his excellent  *
  11.  *  book, "Alogrithms in C", published by Addison Wesley.                   *
  12.  *                                                                          *
  13.  *  The first of the improvements is to always sort the smaller  partition  *
  14.  *  first.  Without  this improvement,  Quicksort can be as slow as Bubble  *
  15.  *  sort in the worst case (a file that is already in sort  order  in  the  *
  16.  *  worst  case  for Quicksort).  The second improvement is to change from  *
  17.  *  the  original  recursive  algorithm  to  an  iterative  algorithm.  By  *
  18.  *  ensuring  that the smaller partition is always sorted first and by not  *
  19.  *  putting the smaller partition on the stack ("end recursion  removal"),  *
  20.  *  we ensure that we need room on the stack for only about log N entries.  *
  21.  *                                                                          *
  22.  *  Another  improvement  used  is to use an insertion sort for partitions  *
  23.  *  less  than  some  rather  arbitrary  size.  Sedgewick  says  that  the  *
  24.  *  algorithm works about the same for sizes from 5 entries to 25 entries.  *
  25.  *  This implementation used 9.                                             *
  26.  *                                                                          *
  27.  *  The  final  improvement  is  to use a "median of three" as the pivotal  *
  28.  *  element.                                                                *
  29.  *                                                                          *
  30.  *  Sedgewick says that the combination of these improvements  results  in  *
  31.  *  an algorithm that is 25% to 30% faster than the basic algorithm on the  *
  32.  *  average.                                                                *
  33.  */
  34.  
  35. #define M 9
  36.  
  37. extern int      (*comp) (const void *a, const void *b);
  38. static void     Sift(char *Array[], int n,
  39.                     int (*comp) (const void *a, const void *b));
  40. static void     Exchange(char *Array[], register int i, register int j);
  41.  
  42.  void
  43. quicksort (char *Array[], int Count, int Width,
  44.           int (*comp) (const void *a, const void *b)) {
  45.     char           *Pivot;
  46.     register int    Left = 0;
  47.     register int    Right;
  48.     register int    i, j;
  49.     register int    StkPtr = 0;
  50.  
  51.     struct {
  52.         int             Left;
  53.         int             Right;
  54.         }               Stack[32];
  55.  
  56.     Right = Count - 1;
  57.     while (1) {
  58.         if ((*comp) (&Array[Left], &Array[Right]) > 0)
  59.             Exchange(Array, Left, Right);
  60.         if ((*comp) (&Array[((Left + Right) / 2)], &Array[Right]) > 0)
  61.             Exchange(Array, ((Left + Right) / 2), Right);
  62.         if ((*comp) (&Array[Left], &Array[((Left + Right) / 2)]) > 0)
  63.             Exchange(Array, Left, ((Left + Right) / 2));
  64.         Exchange(Array, (Left + 1), ((Left + Right) / 2));
  65.         i = Left + 1;
  66.         j = Right;
  67.         Pivot = Array[(Left + 1)];
  68.         while (1) {
  69.             while ((*comp) (&Array[++i], &Pivot) < 0);
  70.             while ((*comp) (&Array[--j], &Pivot) > 0);
  71.             if (i >= j) break;
  72.             Exchange(Array, i, j);
  73.             }
  74.         Exchange(Array, Left, j);
  75.         if (j - Left > Right - j) {
  76.             if (M >= j - Left) {
  77.                 if (StkPtr == 0) break;
  78.                 StkPtr++;
  79.                 Left = Stack[StkPtr].Left;
  80.                 Right = Stack[StkPtr].Right;
  81.                 }
  82.             else {
  83.                 if (Right - j > M) {
  84.                     Stack[StkPtr].Left = Left;
  85.                     Stack[StkPtr].Right = j - 1;
  86.                     StkPtr++;
  87.                     Left = j + 1;
  88.                     }
  89.                 else Right = j - 1;
  90.                 }
  91.             }
  92.         else {
  93.             if (M >= Right - j) {
  94.                 if (!StkPtr) break;
  95.                 StkPtr--;
  96.                 Left = Stack[StkPtr].Left;
  97.                 Right = Stack[StkPtr].Right;
  98.                 }
  99.             else {
  100.                 if (j - Left > M) {
  101.                     Stack[StkPtr].Left = j + 1;
  102.                     Stack[StkPtr].Right = Right;
  103.                     StkPtr++;
  104.                     Right = j - 1;
  105.                     }
  106.                 else Left = j + 1;
  107.                 }
  108.             }
  109.         }
  110.     Sift(Array, Count, comp);
  111.     }
  112.  
  113.  static void
  114. Sift (char *Array[], int Count, int (*comp) (const void *a, const void *b)) {
  115.     register int    i, j;
  116.     char           *c;
  117.  
  118.     for (j = 1; j < Count; ++j) {
  119.         i = j - 1;
  120.         c = Array[j];
  121.         while ((*comp) (&c, &Array[i]) < 0) {
  122.             Array[(i + 1)] = Array[i];
  123.             if (--i < 0) break;
  124.             }
  125.         Array[(i + 1)] = c;
  126.         }
  127.     }
  128.  
  129.  
  130. /*
  131.  * Given an Array[] of pointers to char, exchange its ith and jth elements.
  132.  */
  133.  static void
  134. Exchange (char *Array[], register int i, register int j) {
  135.     char           *temp;
  136.  
  137.     temp = Array[i];
  138.     Array[i] = Array[j];
  139.     Array[j] = temp;
  140.     }
  141.